package com.zh.index.btree.model;

import java.util.Iterator;

/**
 * 分支节点
 * Created by Administrator on 2021/7/28.
 */
public class BranchNode<T extends Comparable> extends Node<T> {

    BranchInnerNode<T> headInnerNode;

    protected BranchNode(BranchInnerNode innerNode) {
        this.headInnerNode = innerNode;
        innerNode.branchNode = this;
        increase();
    }

    /**
     * 查找 t, 如果相同, 则返回 相同的DataNode, 如果没有不同, 则返回小于 t 并且最接近的 dataNode
     * @param t
     * @return
     */
    public DataNode<T> findLeftDataNode(T t) {
        Itr iterator = (Itr) iterator();
        BranchInnerNode<T> temp = null;
        while (iterator.hasNext()) {
            temp = iterator.next();
            if (temp.t.compareTo(t) > 0)
                return temp.leftChildrenNode.findLeftDataNode(t);
        }
        if (temp.t.compareTo(t) > 0)
            return temp.leftChildrenNode.findLeftDataNode(t);
        return temp.getRightChildrenNode().findLeftDataNode(t);
    }

    @Override
    public BranchNode<T> divisionNode(int degree) {
        if (size() < degree)
            return null;
        int center = degree >> 1;
        int i = 0;
        BranchInnerNode belongInnerNode = this.belongInnerNode;
        Iterator<BranchInnerNode<T>> iterator = iterator();
        BranchInnerNode upInnerNode = null;
        BranchNode newBranchNode = null;
        while (iterator.hasNext()) {
            BranchInnerNode<T> temp = iterator.next();
            if (i > center) {
                temp.branchNode = newBranchNode;
                newBranchNode.increase();
            } else if (i == center) {
                upInnerNode = temp;
                temp.leftChildrenNode.belongInnerNode = temp.preInnerNode;
                BranchInnerNode right = iterator.next();
                newBranchNode = new BranchNode(right);

                BranchInnerNode pre = temp.preInnerNode;
                pre.rightChildrenNode = temp.leftChildrenNode;

                // 初始化新的 innerNode
                this.belongInnerNode = upInnerNode;
                newBranchNode.belongInnerNode = upInnerNode;
                upInnerNode.leftChildrenNode = this;
                upInnerNode.rightChildrenNode = newBranchNode;
            }
            i++;
        }
        newBranchNode.setSize(size() - center - 1);
        setSize(center);
        upInnerNode.nextInnerNode.preInnerNode = null;
        upInnerNode.preInnerNode.nextInnerNode = null;
        upInnerNode.nextInnerNode = null;
        upInnerNode.preInnerNode = null;

        if (null == belongInnerNode) {
            BranchNode root = new BranchNode(upInnerNode);
            return root;
        }

        // 非最右边节点
        if (belongInnerNode.t.compareTo(upInnerNode.t) > 0) {
            belongInnerNode.addLeftInnerNode(upInnerNode);
        } else {
            belongInnerNode.addRightInnerNode(upInnerNode);
        }
        return getParentNode().divisionNode(degree);
    }

    @Override
    public Node<T> brorrowOrMergeNode(int degree) {
        return null;
    }


    public Iterator<BranchInnerNode<T>> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<BranchInnerNode<T>> {

        int size = size();
        int index = 0;
        BranchInnerNode<T> temp = headInnerNode;


        @Override
        public boolean hasNext() {
            return index < size;
        }

        @Override
        public BranchInnerNode<T> next() {
            index++;
            BranchInnerNode<T> t = temp;
            temp = temp.nextInnerNode;
            return t;
        }
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        Iterator<BranchInnerNode<T>> iterator = iterator();
        sb.append("(");
        while (iterator.hasNext()) {
            sb.append(iterator.next().toString()).append(",");
        }
        sb.append(")");
        return sb.toString();
    }

}
